package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-21 11:43
 */
public class nextPermutation31 {

    /** 31. 下一个排列
     * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
     * 思路：可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。
     * 我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。
     * 我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。
     * 在尽可能靠右的低位进行交换，需要从后向前查找，将一个 尽可能小的「大数」 与前面的「小数」交换。
     * 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。
     * 算法：
     * 1、从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序--A[i]是从后向前第一个变小的元素，作为需要交换的小数
     * 2、在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k（）。A[i]、A[k] 分别就是上文所说的「小数」、「大数」---A[k]是在i后面第一个比i大的元素，即i和k是从后向前差最小的一对大小数
     * 3、将 A[i] 与 A[k] 交换
     * 4、可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
     * 5、如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
    * */
    public void nextPermutation(int[] nums) {
        if (nums.length<=1) return;
        int n=nums.length;
        int i=n-2,j=n-1,k=n-1;
        //1、从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序--A[i]是从后向前第一个变小的元素，作为需要交换的小数
        for (; i >=0 ; i--,j--) {
            if (nums[i]<nums[j]) break;
        }
        if (i>=0){
            //当前 [begin,end) 不是一个降序顺序，不是最后一个排序
            //在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k（）。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
            while (nums[i]>=nums[k]&&k>=j){
                k--;
            }
            //将 A[i] 与 A[k] 交换
            swap(nums,i,k);
        }
        //4、可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
        reverse(nums,j);
    }
    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }

    void reverse(int[] nums,int start){
        int left=start,right=nums.length-1;
        while (left<right){
            swap(nums,left,right);
            left++;right--;
        }
    }
}
